МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
Лабораторна робота №2
Створення i ведення лiнiйних зв’язаних спискiв iз програмною пiдтримкою пулу вiльної пам’ятi
з курсу: “Алгоритми и структури данних”
Виконав студент
групи КН – 114
Прийняв
ЛЬВІВ 2007
Мета роботи
Ознайомитися iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi лiнiйних зв'язаних спискiв із програмною підтримкою пулу вільного простору.
Теоретичні відомості
Застосування зв’язаного розподілу, як правило, передбачає існування деякого механізму пошуку вільного простору для нового вузла, коли ми хочемо ввести у список деяку нову інформацію. Для цього звичайно використовується спеціальний список, що називається списком вільного простору. Називатимемо цей список списком AVAIL (або стеком AVAIL). Множина всіх вузлів, які у даний момент не використовуються, зв’язана в список, що нічим від інших не відрізняється і змінна AVAIL вказує на його верхній елемент. Тоді, якщо ми хочемо, щоб значенням змінної зв’язку Х стала адреса нового вузла і цей вузол був збережений для подальшого використання, можна зробити так:
Х ( AVAIL, AVAIL ( LINK(AVAIL). (1)
із стека видалється верхній вузол і тепер Х вказує на нього.
Х ( AVAIL - Х стає вказівником на новий вузол.
Якщо вузол більше не потрібний, то для його видалення процес (1) можна виконати так (зворотньо):
LINK(X) (AVAIL, AVAIL ( X. (2)
Ця операція повертає вузол, адреса якого знаходиться у Х, у список заготовок.
Розглядаючи стек AVAIL, ми упустили кілька важливих моментів, наприклад, як побудувати цей стек на початку роботи. Зрозуміло, що це можна зробити,
а) зв’язуючи всі вузли, які будуть використовуватися;
б) заносячи в AVAIL адресу першого з цих вузлів;
в) роблячи зв’язок останнього вузла порожнім.
Множина всіх вузлів, які можуть бути використані, називається пулом пам'яті.
Існує кілька моментів у роботі із стеком AVAIL:
- перевіряти переповнення, тобто чи в (1) вся наявна пам’ять вичерпана. Тоді операцію Х ( AVAIL потрiбно записати так:
Якщо AVAIL = ^ ,то переповнення,
інакше Х ( AVAIL, AVAIL ( LINK(AVAIL).
Можливість переповнення необхiдно враховувати завжди. Якщо виникає переповнення - закiнчуємо роботу.
Часто не відомо наперед скільки місця повинен займати пул пам’яті. Небажано, щоб дiлянка зв’язаної пам’яті займала місця більше ніж потрібно(
Нехай ми хочемо відвести місце для зв’язаної дiлянки, починаючи з Lo у послідовності зростання адрес, і так щоб ця дiлянка ніколи не виходила за межі значення змінної SEQMIN. Тоді, використовуючи нову змінну POOLMAX, можна діяти так:
а) спочатку AVAIL ( ^ ; POOLMASX ( Lo,
б) X ( AVAIL
Якщо AVAIL = ^, то X ( AVAIL, AVAIL ( LINK(AVAIL),
інакше POOLMAX ( POOLMAX+C, де С - розмір вузла; (4)
тепер, якщо POOLMAX > SEQMIN, то переповнення;
інакше Х (-POOLMAX-C.
в) якщо в інших частинах програми зменшується значення SEQMIN, то при SEQMIN < POOLMAX повинен виникнути сигнал переповнення.
г) операція AVAIL (X залишається такою, як і (2).
Суттєвим результатом вищевказаної процедури є використання мінімально можливого пулу пам’яті.
Індивідуальне завдання
Реалізувати пул.
Текст програми:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
const number=10;
//---DATA STRUCTURES--------------
typedef char element_type;
struct unit
{
element_type element;
unit * next;
};
//------FUNCTIONS--------
int full_pool (unit *);
unit * search(unit *);
unit * init_pool(void);
void show_pool(unit *);
unit * delete_from_pool(unit *,unit *);
void insert_pool(unit *,unit **);
//------MAIN-----------------
void main (void)
{
clrscr();
unit * first, *pool;
first=init_pool();
//--if pool was not created---
if (!first) { printf("\n Error can not crete the pool\n"); getch(); goto l1;};
//----------------------------
pool=first;
while (1)
{
printf("\n 1 - enter the element\n 2 - show pool\n 3 - delete symbol\n 4 - exit\n");
int answer;
scanf(" %d",&answer);
switch (answer)
{
case 1:
insert_pool(first,&p...
